package kyssion.leetcode.num1_50;


import java.util.*;

/**
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * <p>
 * 示例:
 * <p>
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
 * 输出:
 * [
 * ["ate","eat","tea"],
 * ["nat","tan"],
 * ["bat"]
 * ]
 * 说明：
 * <p>
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 */
public class code49_字母异位词分组 {
    HashMap<String, Integer> itemList = new HashMap<>();

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> lists = new ArrayList<>();
        for (int a = 0; a < strs.length; a++) {
            char[] item = strs[a].toCharArray();
            Arrays.sort(item);
            String s = new String(item);
            if (!itemList.containsKey(s)) {
                int index = lists.size();
                itemList.put(s, lists.size());
                lists.add(new ArrayList<>());
                lists.get(index).add(strs[a]);
            } else {
                lists.get(itemList.get(s)).add(strs[a]);
            }
        }
        return lists;
    }

    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }

    /**
     * 使用素数进行优化
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams3(String[] strs) {
        List<List<String>> listAll = new ArrayList<List<String>>();
        if (strs.length == 0) {
            return listAll;
        }
        Map<Double, Integer> map = new HashMap<Double, Integer>();
        int a[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        for (int i = 0; i < strs.length; i++) {
            double tmp = 1;
            for (int j = 0; j < strs[i].length(); j++) {
                tmp = tmp * a[strs[i].charAt(j) - 'a'];
            }
            if (map.containsKey(tmp)) {
                listAll.get(map.get(tmp)).add(strs[i]);

            } else {
                map.put(tmp, listAll.size());
                List<String> list = new ArrayList<String>();
                list.add(strs[i]);
                listAll.add(list);
            }

        }
        return listAll;
    }
}
